package 第六周;

/*
 * @author  YxinMiracle
 * @date  2022-05-04 12:39
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.HashMap;
import java.util.Map;

public class 柠檬水找零 {
    public Map<Integer, Integer> billsMap = new HashMap<>();
    public int[] forData = new int[]{20,10,5};
    public boolean lemonadeChange(int[] bills) {
        billsMap.put(20,0);
        billsMap.put(10,0);
        billsMap.put(5,0);
        for (int bill : bills) {
            Integer num = billsMap.get(bill);
            billsMap.put(bill,num+1);
            if (!validate(bill-5)) return false;
        }
        return true;
    }

    private boolean validate(int bill) {
        if (bill == 0) return true;
        for (int datum : forData) {
            while (bill >= datum && billsMap.get(datum)>0){
                bill -= datum;
                Integer num = billsMap.get(datum);
                billsMap.put(datum,num-1);
            }
        }
        return bill == 0;
    }

    public static void main(String[] args) {
        System.out.println(new 柠檬水找零().lemonadeChange(new int[]{5,5,10,10,20}));
    }


}
